算法設計與分析[張德富主編書籍]

《算法設計與分析》是2009年8月1日國防工業出版社出版的圖書，作者是張德富。本書主要取材於算法設計與分析領域的經典內容，介紹了算法設計的發展趨勢。

內容簡介

本書內容主要包括非常經典的算法設計技術，例如遞歸與分治、動態規劃、貪心、回溯、分支限界、圖算法，也包括了一些高級的算法設計主題，例如網路流和匹配、啟發式搜尋、線性規劃、數論以及計算幾何。在算法分析方面，介紹了機率分析以及最新的分攤分析和實驗分析方法。在算法的理論方面，介紹了問題的下界、算法的正確性證明以及NP完全理論等方面的內容。

本書內容基本上涵蓋了目前程式設計競賽所要掌握的算法，並在書後精選了部分ACM國際大學生程式設計競賽的題目，供大家練習。

本書可作為計算機科學系、數學系、軟體學院等專業本科及研究生課程的教材，特別適合於有志於參加程式設計競賽的學生學習和訓練。

圖書目錄

第1章 入門

1.1 問題

1.2 算法的概念

1.3 算法的正確性

1.4 算法的效率

1.5 問題的下界

1.6 小結

習題

實驗題

第2章 漸近符號

2.1 θ符號

2.2 O符號

2.3 η符號

2.4 漸近符號的性質

2.5 常用函式的直觀含義

2.6 小結

習題

第3章 算法分析方法

3.1 機率分析

3.2 分攤分析

3.2.1 合計方法

3.2.2 記賬方法

3.2.3 勢能方法

3.3 實驗分析

3.4 小結

習題

第4章 遞歸

4.1 算法思想

4.1.1 遞歸算法的套用

4.1.2 遞歸與疊代

4.2 遞歸方程的求解

4.2.1 替換方法

4.2.2 遞歸樹方法

4.2.3 式：去

4.3 多項式求值實驗

4.4 小結

習題

實驗題

第5章 分治算法

5.1 算法思想

5.2 合併排序

5.3 快速排序

5.4 大整數乘法

5.5 矩陣乘法

5.6 殘缺棋盤遊戲、

5.7 快速傅立葉變換(FFT)

5.8 小結

習題

實驗題

第6章 動態規劃

6.1 算法思想

6.2 裝配線調度問題

6.3 矩陣鏈乘法問題

6.4 最長公共子序列問題

6.5 0/1背包問題

6.6 最優二叉搜尋樹問題

6.7 動態規劃的基本性質

6.8 小結

習題

實驗題

第7章 貪心算法

7.1 算法思想

7.2 任務選擇問題

7.3 背包問題

7.4 哈夫曼編碼問題

7.5 快取維護問題

7.6 任務選擇問題實驗

7.7 小結

習題

實驗題

第8章 圖算法

8.1 圖的搜尋問題

8.1.1 寬度優先搜尋

8.1.2 深度優先搜尋

8.2 最小生成樹問題

8.2.1 Kruskall算法

8.2.2 Prim算法

8.3 最短路徑問題

8.3.1 單個源點的最短路徑問題

8.3.2 所有點對的最短路徑問題

8.4 小結

習題

實驗題

第9章 網路流與匹配

9.1 最大流問題

9.1.1 FordFulkerson方法

9.1.2 最短路徑增廣算法

9.1.3 Dinic算法

9.1.4 MPM算法

9.1.5 最大流問題的變形

9.2 最小費用流問題

9.2.1 消除迴路算法

9.2.2 最小費用路算法

9.2.3 最小費用路算法的改進

9.3 匹配問題

9.3.1 二分圖匹配

9.3.2 一般圖的匹配

9.4 小結

習題

實驗題

第10章 線性規劃

10.1 線性規劃問題

10.1.1 線性規劃問題的標準形式

10.1.2 線性規劃問題的鬆弛形式

10.2 求解算法

10.2.1 圖解法

10.2.2 單純形算法

10.3 對偶

10.4 小結

習題

實驗題

第11章 NIP完全理論

11.1 判定問題

11.2 P和NP

11.3 NPC

11.3.1 NPC的定義

11.3.2 電路可滿足性問題

11.4 NPC的證明

11.4.1 可滿足性問題

11.4.2 3.CNF可滿足性問題

11。4.3 團問題

11.4.4 頂點覆蓋問題

11.5 其他NP完全問題

11.6 小結

習題

第12章 回溯

12.1 算法思想

12.2 裝載問題

12.3 0/1背包問題

12.4 著色問題

12.5 n皇后問題

12.6 旅行商問題

12.7 流水作業調度問題

12.8 零件切割問題

12.9 小結

習題

實驗題

第13章 分支限界

第14章 啟發式搜尋

第15章 數論

第16章 計算幾何

參考文獻